package link;
import link.SingleLinkList.Node;

import java.math.BigDecimal;

public class LinkExample {

    public static void main(String[] args) {
        SingleLinkList linkList = new SingleLinkList();
        linkList.add(1);
        linkList.add(2);
        linkList.add(3);
        linkList.add(3);
        linkList.add(3);
        linkList.add(5);
        linkList.add(6);
        linkList.add(6);
        linkList.add(6);
        linkList.add(6);
        System.out.println(linkList.toString());
        deleteDuplicates(linkList.getHead());
//        deleteDuplicatesAll(linkList.getHead());
        System.out.println(linkList.toString());
        System.out.println(middleNode(linkList.getHead()).data);
        SingleLinkList linkList1 = new SingleLinkList();
        linkList1.add(1);
        linkList1.add(2);
        linkList1.add(3);
        SingleLinkList linkList2 = new SingleLinkList();
        linkList2.add(2);
        linkList2.add(5);
        linkList2.add(7);
        System.out.println(linkList1.toString());
        System.out.println(linkList2.toString());
        SingleLinkList linkList3 = mergeTwoLists(linkList1, linkList2);
        System.out.println(linkList3.toString());

    }

    /**
     * 删除排序链表中的重复元素
     * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
     */
    public static Node deleteDuplicates(Node head) {
        Node pause = head;
        while (pause.next != null){
            pause = pause.next;
            while (pause.next != null && pause.next.data == pause.data){
                pause.next = pause.next.next;
            }
        }
        return pause;
    }

    /**
     * 删除排序链表中的重复元素
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
     */
    public static Node deleteDuplicatesAll(Node head) {
        Node pause = head;
        while (pause.next != null){
            Node end = pause.next;
            boolean isSame = false;
            while (end != null && end.next != null && end.data == end.next.data){
                end = end.next;
                isSame = true;
            }
            if (isSame) {
                pause.next = end.next;
            }
            if (pause.next != null) {
                pause = pause.next;
            }
        }
        return pause;
    }

    /**
     * 反转链表
     */
    public static Node reverseList(Node head) {
        Node prev  = null; //前指针节点
        Node curr = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            Node nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
            curr.next = prev; //将当前节点指向它前面的节点
            prev = curr; //前指针后移
            curr = nextTemp; //当前指针后移
        }
        return prev;
    }

    /**
     * 合并两个有序链表
     * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public static SingleLinkList mergeTwoLists(SingleLinkList l1, SingleLinkList l2) {
        SingleLinkList list = new SingleLinkList();
        Node pause1 = l1.getHead();
        Node pause2 = l2.getHead();
        while (pause1.next != null || pause2.next != null){
            if (pause2.next == null || (pause1.next != null && pause2.next != null && new BigDecimal(pause1.next.data.toString()).compareTo(new BigDecimal(pause2.next.data.toString())) < 1)){
                list.add(pause1.next.data);
                pause1 = pause1.next;
            }else {
                list.add(pause2.next.data);
                pause2 = pause2.next;
            }
        }
        return list;
    }

    /**
     * 链表的中间结点  快慢指针
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
     * 如果有两个中间结点，则返回第二个中间结点。
     */
    public static Node middleNode(Node head) {
        Node pause = head;
        Node p = head;
        while (p != null && p.next != null){
            pause = pause.next;
            p = p.next.next;
        }
        if (p!=null){
            pause = pause.next;
        }
        return pause;
    }
}
